import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

class Solution {
    static class ListNode{
        int  val;
        ListNode next;

        public int getVal() {
            return val;
        }

        public void setVal(int val) {
            this.val = val;
        }
    }
        public boolean isPalindrome(ListNode head) {
            if(head==null){
                return false;
            }
            ListNode slow=head;
            ListNode fast=head;
            ListNode tmp=null;
            while(fast!=null&&fast.next!=null){
                ListNode pre=slow;
                slow=slow.next;
                fast=fast.next.next;
                pre.next=tmp;
                tmp=pre;
            }
            while(fast!=null&&slow!=null){
                if(fast.val==slow.val){
                    fast=fast.next;
                    slow=slow.next;
                }else{
                    return false;
                }
            }
            return true;
        }
        public List<List<Integer>> threeSum(int[] nums) {
            List<List<Integer>> list=new LinkedList<>();
            int len=nums.length;
            if(len<=2){
                return list;
            }
            Arrays.sort(nums);
            for(int i=0;i<len-2;i++){
                if(nums[i]>0){
                    break;
                }
                if(i>0 &&nums[i]==nums[i-1]){//去重
                    continue;
                }
                int k=i+1;int j=len-1;
                while(k<j){
                    int sum=nums[i]+nums[k]+nums[j];
                    if(sum<0){
                        while(k < j && nums[k] == nums[++k]);
                    }else if(sum>0){
                        while(k < j && nums[j] == nums[--j]);
                    }else{
                        list.add(new ArrayList<>(Arrays.asList
                                (nums[i], nums[k], nums[j])));
                        while(k < j && nums[k] == nums[++k]);
                        while(k < j && nums[j] == nums[--j]);
                    }
                }
            }
            return list;
        }
    public int lengthOfLIS(int[] nums) {
        int len=nums.length;
        if(len==0){
            return 0;
        }
        int [] arr=new int[len];
        Arrays.fill(arr,1);
        int res=0;
        for(int i=0;i<len;i++){
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]){
                    arr[i]=Math.max(arr[i],arr[j]+1);
                }
            }
            res= Math.max(res,arr[i]);
        }
        return res;
    }
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0]);

        LinkedList<int[]> list = new LinkedList<>();
        for (int[] i : people) {
            list.add(i[1], i);
        }
        return list.toArray(new int[list.size()][2]);
    }

    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> list=new LinkedList<>();
        if(s.length()==0||p.length()==0
                ||s.length()<p.length()){
            return list;
        }
        int len=s.length();
        int len1=p.length();
        for(int i=0;i<=len-len1;i++){
            String ret=s.substring(i,len1+i);
            int j=0;
            int a=0;
            int b=0;
            for(j=0;j<ret.length();j++){
                a=a+ret.charAt(j)-'a';
                b=b+p.charAt(j)-'a';
            }
            if(a==b && a!=0 && b!=0){
                list.add(i);
            }
        }
        return list;
    }
}